#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n;
	cin >> n;
	int left[10];
	memset(left,0,sizeof(left));
	int sum = 0;
	for(int i = 1;i <= n;i++){
		int temp;
		cin >> temp;
		sum += temp;
		left[temp % 3]++;
	}
	if(sum % 3 == 0) cout << 0 << "\n";
	if(sum % 3 != 0){
		if(left[sum % 3] != 0){
			cout << 1 << "\n";
		}else{
			if((sum + 1) % 3 == 0){
				cout << 1 << "\n";
			}else{
				cout << 2 << "\n";
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int t;
	cin >> t;
	while(t--) solve();
}